package com.leetcodecn.progrems;


public class FindMedianSortedArrays {
    public static void main(String[] args) {
        int[] arr1 = new int[]{0};
        int[] arr2 = new int[]{0};

        double res = findMedianSortedArrays(arr1,arr2);
        System.out.println("中位数为"+res);
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    //i: nums1的起始位置 j: nums2的起始位置
    public static int findKth(int[] nums1, int i, int[] nums2, int j, int k){
        // 题目中 1 <= m + n
        if( i >= nums1.length) return nums2[j + k - 1];//nums1为空数组
        if( j >= nums2.length) return nums1[i + k - 1];//nums2为空数组
        if(k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if(midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }else {
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }
    }

    //笨比法，时间复杂度爆炸
    /*
    public static float findMedianSortedArrays(int[] nums1, int[] nums2) {
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i : nums1) {
            arr.add(i);
        }
        for (int i : nums2) {
            arr.add(i);
        }
        Collections.sort(arr);

        float res = 0;
        int length = arr.size();
        int mid;
        if (length==0){
            return 0;
        }else if (length%2==1){
            mid = arr.size()/2;
            res = arr.get(mid);
        }else {
            mid = arr.size()/2;
            res = arr.get(mid) + arr.get(mid-1);
            res = res/2;
        }

        return res;
    }
    */
}
